//
// Created by 紫霄 on 2020/5/15.
//

#ifndef LEETCODE_35_H
#define LEETCODE_35_H
class Node {
public:
  int val;
  Node *next;
  Node *random;

  Node(int _val) {
    val = _val;
    next = nullptr;
    random = nullptr;
  }
};
class Solution {
public:
  Node *copyRandomList(Node *head) {
    if (!head)
      return nullptr;
    Node *curNode = new Node(head->val);
    Node *headCopy = curNode, *head1 = head;
    while (head->next) {
      curNode->next = new Node(head->next->val);
      curNode = curNode->next;
      head = head->next;
    }
    head = head1;
    curNode = headCopy;
    while (head) {
      int cnt = 0;
      Node *temp = head1;
      if (head->random) {
        while (temp != head->random) {
          ++cnt;
          temp = temp->next;
        }
        Node *copyTemp = headCopy;
        for (int i = 0; i < cnt; ++i) {
          copyTemp = copyTemp->next;
        }
        curNode->random = copyTemp;
      }
      head = head->next;
      curNode = curNode->next;
    }
    return headCopy;
  }
};
#endif // LEETCODE_35_H
